Backend computing systems have become increasingly complex for enterprises that support many end-users. Examples of such enterprises include social network providers (e.g., LinkedIn and Facebook), banking institutions, and online game providers. In many of these enterprises, system responsiveness is imperative.
One operation that backend computing systems perform is “garbage collection.” In the context of computers, garbage collection (GC) is a form of automatic memory management where a process (or “garbage collector”) attempts to reclaim “garbage” or memory that is occupied by objects that are no longer in use by the program. Garbage collection is often portrayed as the opposite of manual memory management, which requires the programmer to specify which objects to deallocate and return to the memory system. Garbage collection is a significant part, for example, of the Java virtual machine's (JVM's) dynamic memory management system. However, garbage collection may require a substantial portion of total processing time in a device and, as a result, can have significant influence on performance of multiple programs executing on the device.
For example, if a requesting computer (client) sends a request for data to another computer (server) that is in the middle of performing a garbage collection operation (also referred to as “GCing”), then the client may have to wait longer for a response from the server than if the receiver was not GCing.
One approach to avoid sending a request to a GCing server is referred to as the lease approach. Under the lease approach, a client requests a lease before sending a request to a server. If the client receives a lease from a server, then the client can send a request to that server. Otherwise, the client must request a lease from another server. If a server determines to GC, then the server stops giving out leases to clients and invalidates existing leases with clients. This means that no requests are active (at least with respect to the server) while the server is GCing. However, in this approach, there is the overhead of the communication required to request, grant, and revoke leases. In a relatively large distributed system, the number of requests between clients and servers can be significant.
Another disadvantage of the lease approach is referred to as the London Bus problem where servers, over time, tend to all GC at the same time, causing clients to have to wait until there are servers that can grant leases.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.